#include <iostream>

#define Size 10

class MaxHeap
{
public:
    MaxHeap():len(0){}

    void Insert(int value)
    {
        array[len++] = value;//尾插
        SiftUp(len - 1);
    }

    void RemoveRoot()
    {
        if(len == 0)
            return;
        array[0] = array[len - 1];
        SiftDown(0);
        len--;
    }

    int * Search(int value)
    {
        for(int i = 0; i < len; i++)
        {
            if(array[i] == value)
            {
                return &array[i];
            }
        }
        return nullptr;
    }

    int GetMax()
    {
        return array[0];
    }

    void show()
    {
        for(int i = 0; i < len; i++)
        {
            std::cout<<array[i]<<" ";
        }
        std::cout<<std::endl;
    }

private:
//i是指index
    int GetParent(int i){return (i - 1) / 2;}
    int GetLeftChild(int i){return 2 * i + 1;}
    int GetRightChild(int i){return 2 * i + 2;}
/* 上浮操作 */
    void SiftUp(int i)
    {
        // if(i == 0)
        //     return;
        // if(array[i] > array[GetParent(i)])
        // {
        //     std::swap(array[i],array[GetParent(i)]);
        //     SiftUp(GetParent(i));
        // }
        /* 等同上面的递归 */
        while(i > 0 && array[i] > array[GetParent(i)])
        {
            std::swap(array[i],array[GetParent(i)]);
            i = GetParent(i);
        }
    }

    void SiftDown(int i)
    {
        int leftChild = GetLeftChild(i);
        int rightChild = GetRightChild(i);
        int maxIndex = i;
        if(leftChild < len && array[leftChild] > array[i])
        {
            maxIndex = leftChild;
        }
        if(rightChild < len && array[rightChild] > array[maxIndex])
        {
            maxIndex = rightChild;
        }
        if(maxIndex != i)
        {
            std::swap(array[i],array[maxIndex]);
            SiftDown(maxIndex);
        }
    }

    int array[Size];
    int len;
};

int main()
{
    int a[10] = {5, 2, 1, 6, 2, 9, 10, 8, 4, 12};
    MaxHeap heap;
    for(int i = 0; i < 10; i++)
    {
        if(i < 5)
        {
            heap.Insert(a[i]);
        }
        else
        {
            if(heap.GetMax() > a[i])
            {
                heap.RemoveRoot();
                heap.Insert(a[i]);
            }
        }
    }

    // for(int i = 0; i < 6; i++)
    //     heap.Insert(i + 1);
    // heap.show();
    // heap.RemoveRoot();
    // heap.show();
    heap.show();
    return 0;
}